package com.masterlu.leetcode.classic;

import java.util.Collection;
import java.util.Collections;
import java.util.LinkedHashMap;
import java.util.Map;

/**
 * LFU：最不经常使用策略，在一段时间内，数据被使用频次最少，优先被淘汰。
 * 一种用于管理计算机内存的缓存算法。主要记录和追踪内存的使用次数，当缓存已满并且需要更多空间是，系统将以最低内存使用频率清除内存。
 * 最简单使用方法：每个加载到缓存的块分配一个计数器。每次引用该块，计数器加1，当进行内存清理时，系统搜索计数器最低的块并将其从缓存中删除
 *
 * @Author：masterlu
 * @Date：2021/3/20 8:26 下午
 */

public class LeastFrequentlyUsed<K, V> {

    /**
     * 总容量
     */
    private int capaacity;

    private Map<K, Node> caches;

    public LeastFrequentlyUsed(int size) {
        this.capaacity = size;
        this.caches = new LinkedHashMap<K, Node>(size);
    }

    /**
     * 新元素缓存
     *
     * @param key
     * @param value
     */
    public void put(K key, V value) {
        Node node = caches.get(key);
        if (node != null) {
            node.value = value;
            node.modifyAttribute();
        } else {
            if (caches.size() >= capaacity) {
                removeLeastCount();
            }
            caches.put(key, new Node(key, value, System.nanoTime(), 0));
        }
    }


    public V get(K key){
        Node node = caches.get(key);
        if (node== null){
            return null;
        }
       caches.get(key).modifyAttribute();
        return (V) node.getValue();
    }

    /**
     * 缓存池耗尽，删除count最小元素
     */
    private void removeLeastCount() {
        caches.remove(Collections.min(caches.values()).getKey());
    }

    static class Node<K, V> implements Comparable<Node<K, V>> {

        private K key;
        private V value;


        public Node() {
        }

        public Node(K key, V value, long time, int count) {
            this.key = key;
            this.value = value;
            this.time = time;
            this.count = count;
        }

        /**
         * 访问时间
         */
        private long time;
        /**
         * 访问次数
         */
        private int count;


        public K getKey() {
            return key;
        }

        public void setKey(K key) {
            this.key = key;
        }

        public V getValue() {
            return value;
        }

        public void setValue(V value) {
            this.value = value;
        }

        public long getTime() {
            return time;
        }

        public void setTime(long time) {
            this.time = time;
        }

        public int getCount() {
            return count;
        }

        public void setCount(int count) {
            this.count = count;
        }

        /**
         * 对数据数据更新
         */
        public void modifyAttribute() {
            this.count++;
            this.time = System.nanoTime();
        }

        @Override
        public int compareTo(Node<K, V> node) {

            if (this.count != node.getCount()) {
                return this.count - node.getCount();
            }

            return (int) (this.time - node.getTime());
        }
    }


    public static void main(String[] args) {
        LeastFrequentlyUsed<Integer, String> lfuCache = new LeastFrequentlyUsed<>(5);
        lfuCache.put(1,"A");
        lfuCache.put(2,"B");
        lfuCache.put(3,"C");
        lfuCache.put(4,"D");
        lfuCache.put(5,"E");
        lfuCache.put(6,"F");

        System.out.println(lfuCache.get(2));
        System.out.println(lfuCache.get(3));
        System.out.println(lfuCache.get(5));
        System.out.println(lfuCache.get(6));

        lfuCache.put(7,"C");

        System.out.println();
    }
}
